Arithmetic coding is a method for lossless compression of data. Arithmetic coding is based on a probability density function (PDF). For achieving a compression effect, the probability density function on which the coding is based has to be identical to or at least resemble—the closer the better—the actual probability density function which the data actually follows.
If arithmetic coding is based on a suitable probability density function, it may achieve significant compression resulting in at least almost optimal code. Therefore, arithmetic coding is a frequently used technique in audio, speech or video coding for encoding and decoding of coefficient sequences wherein coefficients are quantized time-frequency-transform of video pixels or audio or speech signal sample values in binary representation.
For even improving compression, arithmetic coding may be based on a set of probability density functions, wherein the probability density function used for coding a current coefficient depends on a context of said current coefficient. That is, different probability density functions may be used for coding of a same quantization value in dependency on a context in which the coefficient having said same quantization value appears. The context of a coefficient is defined by the quantization values of coefficients comprised in a neighbourhood of one or more neighbouring coefficients neighbouring the respective coefficient, e.g. a subsequence of one or more already encoded or already decoded coefficients adjacently preceding, in a sequence, the respective coefficient to-be-encoded or to-be-decoded. Each of the different possible appearances the neighbourhood may take defines a different possible context each being mapped onto an associated probability density function.
In practice, said compression improvement becomes manifest only if the neighbourhood is sufficiently large. This comes along with a combinatory explosion of the number of different possible contexts as well as a corresponding huge number of possible probability density functions or a correspondingly complex mapping.
An example of a context based arithmetic coding scheme can be found in ISO/IEC JTC1/SC29/WG11 N10215, October 2008, Busan, Korea, proposing a reference model for Unified Speech and Audio Coding (USAC). According to the proposal, 4-tuples already decoded are considered for context.
Another example of a USAC related context based arithmetic coding can be found in ISO/IEC JTC1/SC29/WG11 N10847, July 2009, London, UK.
For complexity reduction in high order conditional entropy encoding, U.S. Pat. No. 5,298,896 proposes non-uniform quantization of conditioning symbols.